package leetcode.string;

/*
127. 单词接龙

给定两个单词（beginWord?和 endWord）和一个字典，找到从?beginWord 到?endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。

说明:
如果不存在这样的转换序列，返回 0。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出: 5
解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出:0
解释:endWord "cog" 不在字典中，所以无法进行转换。
*/

import java.util.*;

public class LadderLength127 {

    public static void main(String[] args) {

//        String beginWord = "hit";
//        String endWord = "cog";
//        List wordList = Arrays.asList("hit","hot","dot","dog","lot","log","cog");

        String beginWord = "hit";
        String endWord = "cog";
        List wordList = Arrays.asList("hit","hot","dot","tog","cog");

        System.out.println("beginWord: " + beginWord);
        System.out.println("endWord: " + endWord);
        System.out.println("wordList: " + wordList);
        System.out.println(test(beginWord, endWord, wordList));
    }

    public static int test(String beginWord, String endWord, List<String> wordList) {
        if (0 == wordList.size() || !wordList.contains(endWord))
            return 0;

        return settle1(beginWord, endWord, wordList);
    }

    // 单向bfs, 每个单词的每一位使用26个英文字符比较，时间复杂度 O(26 * word-length)
    private static int settle1(String beginWord, String endWord, List<String> wordList) {
        // 构建需要用到的容器
        Set wordSet = new HashSet(wordList);
        Set visited = new HashSet();
        Queue wordQueue = new LinkedList();

        // 初始化工作
        wordSet.remove(beginWord);
        visited.add(beginWord);
        wordQueue.offer(beginWord);

        int queueSize = 0;
        int step = 1;

        while(!wordQueue.isEmpty()) {
            queueSize = wordQueue.size();

            for(int i = 0; i < queueSize; i++) {
                String currentWord = (String) wordQueue.poll();
                char[] charArray = currentWord.toCharArray();

                for(int j = 0; j < endWord.length(); j++) {
                    char originChar = charArray[j];

                    for(char c = 'a'; c <= 'z'; c++) {
                        if(c == originChar)
                            continue;

                        charArray[j] = c;
                        String nextWord = String.valueOf(charArray);

                        if(wordSet.contains(nextWord)) {
                            if (nextWord.equals(endWord))
                                return step + 1;

                            if(!visited.contains(nextWord)) {
                                wordQueue.offer(nextWord);
                                visited.add(nextWord);
                            }
                        }
                    }

                    charArray[j] = originChar;
                }
            }

            step++;
        }

        return 0;
    }
}
